package mo.offer_special;

import java.util.HashMap;
import java.util.Map;

@SuppressWarnings("DuplicatedCode")
public class L064 {

    private TrieNode root;

    /** Initialize your data structure here. */
    public L064() {
        root = new TrieNode();
    }

    public void buildDict(String[] dictionary) {
        for (String word : dictionary) {
            TrieNode cur = root;
            for (char c : word.toCharArray()) {
                int idx = c - 'a';
                if (cur.children[idx] == null) {
                    cur.children[idx] = new TrieNode();
                }
                cur = cur.children[idx];
            }
            cur.end = true;
        }
    }

    public boolean search(String searchWord) {
        TrieNode cur = root;
        for (int i = 0; i < searchWord.length(); ++i) {
            int curIdx = searchWord.charAt(i) - 'a';

            for (int x = 0; x < 26; x++) {
                if (x == curIdx || cur.children[x] == null) {
                    continue;
                }

                //替换的树节点作为根节点
                if (contains(cur.children[x], searchWord.substring(i+1))) {
                    return true;
                }
            }

            //查询的字符在前缀树中没有
            if (cur.children[curIdx] == null) {
                return false;
            }
            cur = cur.children[curIdx];
        }
        return false;
    }

    private boolean contains(TrieNode node, String word) {
        for (int i = 0; i < word.length(); ++i) {
            int num = word.charAt(i) - 'a';
            if (node.children[num] == null) {
                return false;
            }
            node = node.children[num];
        }
        return node.end;
    }

    private static class TrieNode {
        boolean end;
        TrieNode[] children = new TrieNode[26];
    }

}
